package Sort;

public class HeapSort {
    private static void heapSort(int[] arr) {
        //此处-1是因为数组下表从0开始
        int len = arr.length -1;
        for(int i = len/2 - 1; i >=0; i --){ //堆构造
            heapAdjust(arr,i,len);
        }
        while (len >=0){
            swap(arr,0,len--);    //将堆顶元素与尾节点交换后，长度减1，尾元素最大
            heapAdjust(arr,0,len);    //再次对堆进行调整
        }
    }

    public static  void heapAdjust(int[] arr,int i,int len){
        int left,right,j ;
        while((left = 2*i+1) <= len){    //判断当前父节点有无左节点（即有无孩子节点，left为左节点）
            right = left + 1;  //右节点
            j = left;   //j"指针指向左节点"
            if(j < len && arr[left] < arr[right])    //右节点大于左节点
                j ++;     //当前把"指针"指向右节点
            if(arr[i] < arr[j])    //将父节点与孩子节点交换（如果上面if为真，则arr[j]为右节点，如果为假arr[j]则为左节点）
                swap(arr,i,j);
            else         //说明比孩子节点都大，直接跳出循环语句
                break;
            i = j;
        }
    }
    public static  void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        int array[] = {20,50,20,40,70,10,80,30,60};
        System.out.println(7/2);
        System.out.println("排序之前：");
        for(int element : array){
            System.out.print(element+" ");
        }
        myHeapSort(array);
        System.out.println("\n排序之后：");
        for(int element : array){
            System.out.print(element+" ");
        }
    }


    private static void myHeapSort(int a[]){

        //第一次构建堆 减1是为了从0对应下标
        int length = a.length-1;
        for(int i = a.length/2-1;i>=0;i--){
            myHeapAdjust(a,i,length);
        }

        while(length>=0){
            swap(a,0,length--);
            myHeapAdjust(a,0,length);
        }

    }

    /**
     * @MethodName myHeapAdjust
     * @Date:2018/9/16 22:51
     * @Parm:[a, i, length]
     * @Return:void
     * @Description:
     */
    private static void myHeapAdjust(int[] a, int i, int length) {
        int left,right,j;

        while ((left = 2*i+1)<=length){
            right = left+1;
            j = left;
            if(j < length && a[left]<a[right]){
                j = right;
            }
            if(a[j]>a[i]){
                swap(a,i,j);
            }else{
                break;
            }
            //break的话就走不到这一步
            i=j;
        }

    }

}